// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-06 13:17
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreePaths {
    List<String> ans = new ArrayList<>();

    /**
     * 获取二叉树所有根节点到叶子结点的路径
     */

    public List<String> binaryTreePaths(TreeNode root) {
        // 使用DFS进行遍历，结束标记为到达叶子节点
        // 路径存储使用字符串
        DFS(root, "");
        return ans;
    }

    /**
     * 获取所有从根节点到叶子节点的路径，并且存储在指定列表中
     *
     * @param root 根节点
     * @param path 结果列表
     */
    private void DFS(TreeNode root, String path) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            // 到达叶子节点，当前路径结束
            path += (root.val);
            ans.add(path);
            return;
        }
        path += (root.val + "->");
        DFS(root.left, path);
        DFS(root.right, path);
    }

    @Test
    public void shout() {
        int[] nodes = {1, 2, 3, -1, 5};
        Utils utils = new Utils();
        TreeNode<Integer> root = utils.constructTreeBySequence(nodes);
        System.out.println(binaryTreePaths(root));
    }


}
